/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\236.二叉树的最近公共祖先.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-04-09 10:48:14
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-04-09 11:37:22
 */
/*
 * @lc app=leetcode.cn id=236 lang=cpp
 *
 * [236] 二叉树的最近公共祖先
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// class Solution {
// public:
//     TreeNode *ans;
//     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//         dfs(root,p,q);
//         return ans;
//     }

//     bool dfs(TreeNode* root,TreeNode* p,TreeNode* q)
//     {
//         if(root == NULL)
//         {
//             return false;
//         }
//         bool lson = dfs(root->left,p,q);
//         bool rson = dfs(root->right,p,q);
//         if((lson && rson )|| ((root->val == p->val || root->val == q->val) && (lson || rson)) )
//         {
//             // 公共祖先
//             ans = root;
//         }
//         return lson || rson || root->val == p->val || root->val == q->val;
//     }
// };


class Solution {
public:
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
        {
            return NULL;
        }
        if(root->val == p->val || root->val == q->val)
        {
            return root;
        }
        TreeNode *lson = lowestCommonAncestor(root->left,p,q);
        TreeNode *rson = lowestCommonAncestor(root->right,p,q);
        if(lson!=NULL && rson!=NULL)
        {
            return root;
        }
        else if(lson == NULL)
        {
            return lowestCommonAncestor(rson,p,q);
        }else
        {
            return lowestCommonAncestor(lson,p,q);
        }
        return NULL;

    }

};



// @lc code=end
 
